/**
 * 旋转图像
 *
 * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 *
 * 示例 1：
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[[7,4,1],[8,5,2],[9,6,3]]
 *
 * 示例 2：
 * 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
 * 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 *
 * 提示：
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 20
 * -1000 <= matrix[i][j] <= 1000
 */

/**
 * 这一题也是同样的画图找规律, 也没啥好找的规律, 我们就按照一开始的能想到的
 * 的来, 我们首先将第一行顺时针旋转 90, 在将最后一列顺时针旋转 90 , 注意
 * 因为不能有额外数组的原因, 我们需要原地修改, 这就要我们交换数组中的元素了
 * 我们依然按照上面的方法来交换数组, 后面我们会发现, 这个时候我们只需要按照刚才
 * 的规律将第一行和最后一行交换一下就是旋转数组了, 我们在写的时候需要留一个心眼子
 * 这只是最表面的一层, 我们还需要处理里面的, 所以用一个 k 来记录我们处理的层数
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        int[][] nums = new int[][]{
                { 1,  2,  3,  4},
                { 5,  6,  7,  8},
                { 9, 10, 11, 12},
                {13, 14, 15, 16},
        };
        test.rotate(nums);
    }

    public void rotate(int[][] matrix) {

        // 矩阵长
        int n = matrix.length;

        // 记录我们处理到第几层
        int k = 0;
        for (int i = n; i > 0; i--) {

            // 这里我们不然 j 从 k 开始, 是因为里面层的最后一行, 我们在从右向左遍历时, 需要一个一个减
            // 要是 j 从 k 开始就找不到值了, 所以我们让 j 从 0开始, 后面要是出现 从k 开始的数字, 我们让 j
            // 加上 k 就好了
            for (int j = 0; j < i - 1 - k; j++) {

                // 这里的下标对应, 仔细一点, 画图自然可以解决

                // 第一行 从左到右
                swap(matrix, k, j + k, j + k, i - 1);

                // 最后一列 从上到下
                swap(matrix, i - 1, i - 1 - j, i - 1 - j, k);

                // 最后一行 从右到左
                swap(matrix, k, j + k, i - 1, i - 1 - j);

                // 这里的正好可以一起处理, 按照这个规律, 真是巧了
            }

            // 这里处理完一层 ++
            k++;
        }
    }

    // 交换数组中的值
    private void swap (int[][] matrix, int i1, int j1, int i2, int j2) {
        int tmp = matrix[i1][j1];
        matrix[i1][j1] = matrix[i2][j2];
        matrix[i2][j2] = tmp;
    }
}